package leetcode.tree;

import java.util.HashMap;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal106 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution1 {
        HashMap<Integer,Integer> memo = new HashMap<>();
        int[] post;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            for(int i = 0;i < inorder.length; i++) {
                memo.put(inorder[i], i);
            }
            post = postorder;
            TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);
            return root;
        }

        public TreeNode buildTree(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
            if(inorderEnd < inorderStart || postorderEnd < postorderStart) return null;

            int root = post[postorderEnd];
            int ri = memo.get(root);

            TreeNode node = new TreeNode(root);
            node.left = buildTree(inorderStart, ri - 1, postorderStart, postorderStart + ri - inorderStart - 1);
            node.right = buildTree(ri + 1, inorderEnd, postorderStart + ri - inorderStart, postorderEnd - 1);
            return node;
        }
    }

    class Solution2 {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                hashMap.put(inorder[i], i);
            }
            return buildTree(0, inorder.length - 1, 0, postorder.length - 1, hashMap, postorder);
        }

        public TreeNode buildTree(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd, HashMap<Integer, Integer> hashMap, int[] postorder) {
            if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
                return null;
            }
            int valOfRoot = postorder[postorderEnd];
            int indexOfRoot = hashMap.get(valOfRoot);
            TreeNode root = new TreeNode(valOfRoot);
            root.left = buildTree(inorderStart, indexOfRoot - 1, postorderStart, postorderStart + indexOfRoot - inorderStart - 1, hashMap, postorder);
            root.right = buildTree(indexOfRoot + 1, inorderEnd, postorderStart + indexOfRoot - inorderStart, postorderEnd - 1, hashMap, postorder);
            return root;
        }
    }
}
